1. Field of the Invention
The present invention relates generally to a rotationally invariant correlator, and more particularly pertains to a rotationally invariant correlator which is designed to correlate an arbitrarily rotated image with a large database of similar stored images.
2. Discussion of the Prior Art
The present invention was invented to solve a particular problem faced by the Federal Bureau of Investigation (FBI) in their "Drug Fire" program, whereby the unique features of the physical impression made by a firing pin of a particular firearm weapon on the firing ring (cartridge primer) of a bullet casing is used to identify the particular weapon which fired that bullet. The present invention was conceived to analyze and match the characteristics of a firing ring of a discharged or fired bullet cartridge with the characteristics of firing rings of discharged bullet cartridges in memory to determine if a match can be made. Each gun has a firing pin which impacts against the firing ring or cartridge primer of a bullet cartridge to discharge or fire the bullet. Each gun and firing pin creates a slightly different pattern in the firing ring of a bullet cartridge which is a characteristic signature (fingerprint) of that gun. Thus, by analyzing the pattern in the firing ring of a discharged bullet cartridge, and comparing it with the patterns in the firing rings of other discharged bullet cartridges, one can determine if the same gun fired two different discharged bullet cartridges.
A conventional image matching technique applied to the above correlation situation would produce a Fast Fourier Transform (FFT) for the entire image of the firing ring of the discharged bullet cartridge and compare it with Fast Fourier Transforms in memory for images of firing rings of discharged bullet cartridges. This conventional image matching technique is very time consuming compared with the rotationally invariant correlator of the present invention. The reduction in complexity of the rotationally invariant correlator of the present invention when compared with conventional image matching techniques can be quite dramatic. For example, assume that an image consists of N.sup.2 pixels, which is to be compared against a library of M images. Since the rotation of the image is unknown, the image to be compared must be quantized into n possible rotations. Therefore, in conventional image matching, an order of n.times.M.times.N.sup.2 image matching correlating operations must be performed. With the present invention, the number of image matching operations is reduced by a factor of n. For example, if n=360 (one degree steps), the complexity and number of correlations is reduced by over two orders of magnitude. In one test, the present invention accomplished image matching in a database in 90 seconds, compared with 30 hours of image matching in the same database using the above conventional image matching technique.